class BankersAlgorithm:
    def __init__(self, available, max_demand, allocation):
        """
        初始化银行家算法
        
        参数:
        available: 可用资源向量，表示每种资源的可用数量
        max_demand: 最大需求矩阵，每个进程对每种资源的最大需求
        allocation: 分配矩阵，当前已分配给每个进程的资源数量
        """
        self.available = available
        self.max_demand = max_demand
        self.allocation = allocation
        self.n = len(max_demand)  # 进程数量
        self.m = len(available)   # 资源类型数量
        
        # 计算需求矩阵
        self.need = []
        for i in range(self.n):
            need_i = [self.max_demand[i][j] - self.allocation[i][j] for j in range(self.m)]
            self.need.append(need_i)
    
    def is_safe_state(self):
        """检查系统是否处于安全状态"""
        work = self.available[:]  # 工作向量
        finish = [False] * self.n  # 标记进程是否完成
        
        safe_sequence = []  # 安全序列
        
        # 寻找可以执行的进程
        while len(safe_sequence) < self.n:
            found = False
            for i in range(self.n):
                if not finish[i] and self._can_allocate(i, work):
                    # 进程i可以执行，释放其资源
                    for j in range(self.m):
                        work[j] += self.allocation[i][j]
                    finish[i] = True
                    safe_sequence.append(i)
                    found = True
                    break
            
            if not found:
                # 没有找到可以执行的进程，系统不安全
                return False, []
        
        return True, safe_sequence
    
    def request_resources(self, process_id, request):
        """
        处理进程的资源请求
        
        参数:
        process_id: 请求资源的进程ID
        request: 请求的资源向量
        
        返回:
        (是否批准, 安全序列)
        """
        # 检查请求是否超过进程的最大需求
        for j in range(self.m):
            if request[j] > self.need[process_id][j]:
                return False, f"错误：进程{process_id}请求的资源超过其最大需求"
        
        # 检查系统是否有足够的可用资源
        for j in range(self.m):
            if request[j] > self.available[j]:
                return False, f"错误：系统没有足够的资源满足进程{process_id}的请求"
        
        # 尝试分配资源
        for j in range(self.m):
            self.available[j] -= request[j]
            self.allocation[process_id][j] += request[j]
            self.need[process_id][j] -= request[j]
        
        # 检查分配后系统是否安全
        is_safe, safe_sequence = self.is_safe_state()
        
        if is_safe:
            return True, safe_sequence
        else:
            # 如果不安全，回滚分配
            for j in range(self.m):
                self.available[j] += request[j]
                self.allocation[process_id][j] -= request[j]
                self.need[process_id][j] += request[j]
            return False, "错误：分配会导致系统进入不安全状态"
    
    def _can_allocate(self, process_id, work):
        """检查是否可以分配资源给指定进程"""
        for j in range(self.m):
            if self.need[process_id][j] > work[j]:
                return False
        return True
    
    def display_state(self):
        """显示当前系统状态"""
        print("\n当前系统状态:")
        print(f"可用资源: {self.available}")
        print("\n进程\t最大需求\t已分配\t需求")
        for i in range(self.n):
            print(f"P{i}\t{self.max_demand[i]}\t\t{self.allocation[i]}\t{self.need[i]}")


# 示例使用
if __name__ == "__main__":
    # 初始化参数
    # 3种资源，可用数量分别为10, 5, 7
    available = [10, 5, 7]
    
    # 5个进程的最大需求
    max_demand = [
        [7, 5, 3],
        [3, 2, 2],
        [9, 0, 2],
        [2, 2, 2],
        [4, 3, 3]
    ]
    
    # 当前已分配的资源
    allocation = [
        [0, 1, 0],
        [2, 0, 0],
        [3, 0, 2],
        [2, 1, 1],
        [0, 0, 2]
    ]
    
    # 创建银行家算法实例
    banker = BankersAlgorithm(available, max_demand, allocation)
    
    # 显示初始状态
    banker.display_state()
    
    # 检查系统是否安全
    is_safe, sequence = banker.is_safe_state()
    if is_safe:
        print(f"\n系统处于安全状态，安全序列: {['P'+str(i) for i in sequence]}")
    else:
        print("\n系统处于不安全状态！")
    
    # 测试资源请求
    print("\n--- 测试资源请求 ---")
    
    # 进程1请求资源 [1, 0, 2]
    process_id = 1
    request = [1, 0, 2]
    print(f"进程{process_id}请求资源: {request}")
    
    approved, result = banker.request_resources(process_id, request)
    
    if approved:
        print(f"请求批准！安全序列: {['P'+str(i) for i in result]}")
        banker.display_state()
    else:
        print(f"请求被拒绝: {result}")
    
    # 测试会导致不安全的请求
    print("\n--- 测试不安全请求 ---")
    
    # 进程0请求大量资源 [7, 4, 3]
    process_id = 0
    request = [7, 4, 3]
    print(f"进程{process_id}请求资源: {request}")
    
    approved, result = banker.request_resources(process_id, request)
    
    if approved:
        print(f"请求批准！安全序列: {['P'+str(i) for i in result]}")
        banker.display_state()
    else:
        print(f"请求被拒绝: {result}")